package com.algorithm.ch1.lzr.string;

/**
 * 给定一个字符串, 找到它的第一个不重复的字符, 并返回它的索引
 * 如果不存在,则返回 -1
 * <p>
 * 关键点: 给定字符串全部都为小写字母
 * <p>
 * <p>
 * s = "leetcode"
 * 返回 0.
 * <p>
 * <p>
 * s = "loveleetcode",
 * 返回 2.
 *
 * @author lzr
 * @date 2018/8/10
 */
public class FirstUniqChar {

    public static void main(String[] args) {
        int index1 = firstUniqChar1("leetcode");
        int index2 = firstUniqChar2("leetcode");

        System.out.println(index1);
        System.out.println(index2);
    }

    /**
     *
     * @param s
     * @return
     */
    public static int firstUniqChar1(String s) {
        if (s.length() == 0) {
            return -1;
        }
        if (s.length() == 1) {
            return 0;
        }
        //将字符串转成字符数组
        char[] chars = s.toCharArray();
        //存储字母
        int[] temp = new int[26];
        //存储字母对应索引
        int[] index = new int[26];
        for (int i = 0; i < chars.length; i++) {
            //有重复数字
            temp[chars[i] - 97]++;
            index[chars[i] - 97] = i;
        }
        //索引排序 找到最小值
        int[] min = new int[chars.length];
        for (int i = 0; i < temp.length; i++) {
            //没有重复的数字
            if (temp[i] == 1) {
                min[index[i]] = 1;
            }
        }
        for (int i = 0; i < min.length; i++) {
            if (min[i] == 1) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 字符串只有小写英文字母
     *
     * @param s
     * @return
     */
    private static int firstUniqChar2(String s) {
        int result = -1;
        for (char c = 'a'; c <= 'z'; c++) {
            //获取每个字符所在位置,字符串没有该字符则返回-1,有则返回字符所在位置
            int index = s.indexOf(c);
            //如果s.indexOf(c) == s.lastIndexOf(c) 则代表字符在字符串中唯一
            if (index != -1 && index == s.lastIndexOf(c)) {
                result = result == -1 ? index : Math.min(result, index);
            }
        }
        return result;
    }
}
